package book;

import java.util.Arrays;

public class StampSolution {
    public int minStamps(int[] stamps, int amount) {
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        for (int i = 0; i < amount; ++i) {
            if (dp[i] >= 0) { // 细节1：dp[i]==-1表示没有任何方法可以凑出面额i，这时计算就要跳过
                for (int c: stamps) {
                    if (c <= amount - i) { // 细节2：当心数组越界
                        int s = i + c; // 当前新的面额
                        int cnt = dp[i] + 1; // 组成面额a所需的硬币数
                        if (dp[s] == -1 || dp[s] > cnt) 
                            dp[s] = cnt;
                    }
                }
            }
        }
        return dp[amount];
    }    

    public static void main(String[] args) {
        int[] stamps = { 1, 6, 10 };
        int amount = 13;
        int a = new StampSolution().minStamps(stamps, amount);
        System.out.println("最小邮票张数: " + a);
    }
}
